package vj.recursion;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class PowerSet {

	public static void main(String[] args) {
		String st[] = { "c", "d", "e", "f", "g", "h", "i", "j", "k", "l" /*, "m", "n", "o", "p", "q"*/};
		System.out.println(powerSet(st));
	}
	
	public static Set<Set<String>> powerSet(String[] st) {
		Set<Set<String>> pSet = new HashSet<Set<String>>();
		int len = st.length;
		int elements = (int) Math.pow(2, len);
		for (int i = 0; i < elements; i++) {
			String str = Integer.toBinaryString(i);
			int value = str.length();
			String pset = str;
			for (int k = value; k < len; k++) {
				pset = "0" + pset;
			}
			Set<String> set = new HashSet<String>();
			for (int j = 0; j < pset.length(); j++) {
				if (pset.charAt(j) == '1')
					set.add(st[j]);
			}
			pSet.add(set);
		}
		return pSet; 
	}

	public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
		Set<Set<T>> sets = new HashSet<Set<T>>();
		if (originalSet.isEmpty()) {
			sets.add(new HashSet<T>());
			return sets;
		}
		List<T> list = new ArrayList<T>(originalSet);
		T head = list.get(0);
		Set<T> rest = new HashSet<T>(list.subList(1, list.size()));
		for (Set<T> set : powerSet(rest)) {
			Set<T> newSet = new HashSet<T>();
			newSet.add(head);
			newSet.addAll(set);
			sets.add(newSet);
			sets.add(set);
		}
		return sets;
	}
}
